実行可能性の幾何学
等式制約 $Ax = b$ を持つ凸問題について、ベクトル $v \in \mathbf{R}^n$ が 実行可能方向 であるとは、$Av = 0$ のときを指します。これは、方向 $v$ に移動しても制約が維持されることを意味します：$Ax = b$ ならば $A(x + v) = b$ です。
$x^*$ が最適となるためには、$\mathcal{N}(A)$ 内のすべての実行可能方向 $v$ に対して、方向微分 $\nabla f(x^*)^T v$ がゼロでなければなりません。これは、勾配 $\nabla f(x^*)$ が $\mathcal{N}(A)$ に直交していることを意味し、 ラグランジュ乗数の存在へと導きます。
ある点 $x^*$ が最適であるのは、$\nu^* \in \mathbb{R}^p$ となるベクトルが存在するときのみであり、その条件は次のように表されます：
$\nabla f(x^*) + A^T \nu^* = 0$
これは、目的関数の下降方向と制約の多様体との間の均衡を特徴づける連立線形方程式系を形成します。
投影勾配
負の勾配 $-\nabla f(x)$ ユークリッド射影 を $\mathcal{N}(A)$ に射影した結果は次の通りです：
$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$
このベクトルは「最良」の実行可能降下方向を表します。重要なのは、$x$ が最適であるのは、$\Delta x_{\text{pg}} = 0$ であるときだけであるということです。
KKTシステムと行列の性質
ブロックシステムを用いて、ニュートンステップと双対変数を同時に解くことができます：
$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$行列のスペクトル特性に関する注意： KKT行列は対称ですが、 不定です。行列が非特異な場合、正確に $n$ 個の正の固有値と $p$ 個の負の固有値を持ちます。これは、最適点 $(x^*, \nu^*)$ がラグランジアン $L(x, \nu) = f(x) + \nu^T(Ax-b)$ に対する 鞍点 であり、結合されたプライマル・デュアル空間における単純な局所最小値ではありません。